/*
 * @lc app=leetcode.cn id=23 lang=cpp
 *
 * [23] 合并K个升序链表
 */
#include "include.h"

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// @lc code=start
class Solution {
public:
    // struct Comp {
    //     bool operator() (ListNode* l1, ListNode* l2) {
    //         return l1->val > l2->val;
    //     }
    // };
    // ListNode* mergeKLists(vector<ListNode*>& lists) {
    //     if (lists.empty()) return nullptr;
    //     priority_queue<ListNode*, vector<ListNode*>, Comp> q;
    //     for (ListNode* list: lists) {
    //         if (list) {
    //             q.push(list);
    //         }
    //     }
    //     ListNode* dummy = new ListNode(0), *cur = dummy;
    //     while (!q.empty()) {
    //         cur->next = q.top();
    //         q.pop();
    //         cur = cur->next;
    //         if (cur->next) {
    //             q.push(cur->next);
    //         }
    //     }
    //     return dummy->next;
    // }

    /** 
     * 这个
     * priority_queue <Status> q;
     * 
     * 果然这道题用map也可以
     * 底层红黑树在insert时会按插入pair的第一位从小到大排序
     * 多个key相同时需要multiple_map
     * 
     * 一个比较有趣的地方就是
     * 完全可以从最终结果起点前一位新建一个结点，免去了一次初始判断
     * 最后只要返回这个new出来的结点的next指针就好了
     * 做题就new就完事了，反正这堆又不在我电脑上
     * 
     * 但是还是看一下priority_queue吧
     * 这个的底层貌似是用vector做的堆排序
     * 方法就empty()\push()\pop()\top()还有个size()
     * 用起来更简单一些
    **/
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // ListNode* result = nullptr;
        // ListNode* end = nullptr;

        ListNode* result = new ListNode(0);
        ListNode* end = result;

        int n = lists.size();
        
        // I need a priority queue, which is continuiously 
        // being sorted when inserted
        multimap<int, ListNode*> waitingQueue;
        
        for (int i=0;i<n;++i){
            if (lists[i]){
                waitingQueue.insert(make_pair(lists[i]->val, lists[i]));
                lists[i] = lists[i]->next;
            }
        }
        
        while(!waitingQueue.empty()){
            end->next = waitingQueue.begin()->second;
            waitingQueue.erase(waitingQueue.begin());
            end = end->next;
            if (end->next != nullptr){
                waitingQueue.insert(make_pair(end->next->val, end->next));
            }       
        }

        return result->next;
    }
};
// @lc code=end

